package com.otherTest.sort;

import org.junit.Test;

/**
 * 快速排序
 *
 * @author Conceit
 * @version 1.0, 2017/3/20
 */
public class FastSort {


    /**
     * 通过一趟排序将待排序记录分割成独立的两部分
     * 其中一部分记录的关键字均比另一部分关键字小
     * 则分别对这两部分继续进行排序
     * 直到整个序列有序
     */
    public synchronized void fastsort(int [] ints) {
        int sort[] = {6, 1, 11, 7, 9, 3, 4, 5, 10, 8, 2};
        if(ints.length==0){
            sort=ints;
        }
        //定义基准数
        //基准位置的选取 固定切分，随机切分和三取样切分
        //固定切分的效率并不是太好
        // 随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N2)
        // 对于三数取中选择基准点是最理想的一种。

        //使用java自带的快速排序方法
//        Arrays.sort(sort);
//        for(int i:sort){
//            System.out.println(i);
//        }
        //手动完成快速排序
        doFastSort(ints, 0, ints.length - 1);
    }

    /**
     * 执行快速排序
     *
     * @param array 原始数组
     * @param low   低位index
     * @param high  高位index
     */

    public void doFastSort(int[] array, int low, int high) {
        //数据的准确性进行校验
        if (low > high) {
            return;
        }

        //定义基准值
        int base = array[low];

        //低位下标以及高位下标
        int l = low;
        int h = high;

        //如果条件正确则进行遍历
        while (l < h) {
            //高位下标向左移动，进行比较
            for (; ; h--) {
                //高位下标如果小于地位下标，则不用进行计算,或者说是退出条件
                if (h <= l) {
                    break;
                }
                //如果当前数组中高位下标小于基准值，则进行交换
                if (array[h] < base) {
                    array[l] = array[h];
                    break;
                }
            }
            //处理地位下标,与高位下标相反
            for (; ; l++) {
                //高位下标如果大于地位下标，则不用进行计算,或者说是退出条件
                if (l >= h) {
                    break;
                }
                //如果当前数组中低位下标大于基准值，则进行交换
                if (array[l] > base) {
                    array[h] = array[l];
                    break;
                }
            }
            //没有递归前最终的结果：2，1，5，4，3(low)，3(high)，9，7，10，8，11
            //print(array);
            //若低位和高位值相等,将基准值赋予给低位或者high,不然会有两个相等的值
            if(l==h){
                array[l]=base;
            }
            //递归处理
            //low之前的下标继续分组
            doFastSort(array,low ,l-1 );
            //high之后的下标继续分组
            doFastSort(array,l+1 ,high );
        }

//        print(array);



    }

    /**
     * 辅助方法
     *
     * @param array
     */
    public void print(int[] array) {

        int count=array.length;
        for (int i : array) {
            System.out.println(i);
        }
        System.out.println("排序正在进行----共"+count+"次");

    }


    /**
     * 通过一趟排序将待排序记录分割成独立的两部分
     * 其中一部分记录的关键字均比另一部分关键字小
     * 则分别对这两部分继续进行排序
     * 直到整个序列有序
     */
    @Test
    public void fastSort2(){
        int sort[] = {6, 1, 11, 7, 9, 3, 4, 5, 10, 8, 2};
        //低位下标
        int low=0;
        //高位下标
        int high=sort.length-1;
        //输出
        doFastSort2(sort,low,high);
        }

      
    
    
    /**
     * 执行快速排序方法2
     *
     * @param ints 原始数组
     * @param low  低位下标
     * @param high  高位小标
     */
    public void doFastSort2(int[] ints,int low,int high){


        
         //需要调换的高低位下标,方法开始是即是高低位
         int currentLowIndex=low;
         int currentHighIndex=high;
         int currentBase=ints[low];

        //高位小于低位退出循环
        while(currentLowIndex<currentHighIndex){

            //高位循环 由高向低先执行
            for(;;currentHighIndex--){

                //比较下标位置
                if(currentLowIndex>=currentHighIndex){
                    break;
                }

                //比较下标值,是否大于小于基准值
                if(ints[currentHighIndex]<currentBase){
                    //进行高低下标值交换
                    ints[currentLowIndex]=ints[currentHighIndex];
                    break;
                }

            }

            //低位循环 由低向高后执行
            for(;;currentLowIndex++){
                //比较下标位置
                if(currentLowIndex>=currentHighIndex){
                    break;
                }

                //比较下标值,是否大于小于基准值
                if(ints[currentLowIndex]>currentBase){
                    //进行交换
                    ints[currentHighIndex]=ints[currentLowIndex];
                    break;
                }

            }

            //若发生高低位指针碰撞,则将基准值重新赋值给低位下标值
            if(currentLowIndex==currentHighIndex){
                ints[currentLowIndex]=currentBase;
            }

            //递归,高低下标分别执行
            //低位
            doFastSort2(ints,low,currentLowIndex-1);
            //高位
            doFastSort2(ints,currentLowIndex+1,high);

        }

        print(ints);
    }

    
}
